package com.example.dfs;

import com.example.structure.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 剑指 Offer 34. 二叉树中和为某一值的路径
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 * <p>
 * 示例:
 * 给定如下二叉树，以及目标和 target = 22，
 * <p>
 * 5
 * / \
 * 4   8
 * /   / \
 * 11  13  4
 * /  \    / \
 * 7    2  5   1
 * 返回:
 * <p>
 * [
 * [5,4,11,2],
 * [5,8,4,5]
 * ]
 */
public class PathSum {
    List<List<Integer>> result = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return result;
    }

    public void dfs(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0) {
            result.add(new LinkedList<>(path));
        }
        dfs(root.left, target);
        dfs(root.right, target);
        path.pollLast();
    }

    public void back(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        path.addLast(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0) {
            result.add(new LinkedList<>(path));
        }
        dfs(root.left, target);
        dfs(root.right, target);
        path.removeLast();

    }
}

/**
 * 面试题 04.12. 求和路径   此题和剑指 Offer 34. 二叉树中和为某一值的路径区别是 这个题求的不是叶子节点，而是任何有可能的路径，
 * 所以就需判定时去掉叶子节点的判定，并且开始递归时要递归套递归，使每个节点都可能使根节点
 * <p>
 * <p>
 * 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
 * <p>
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 * <p>
 * 5
 * / \
 * 4   8
 * /   / \
 * 11  13  4
 * /  \    / \
 * 7    2  5   1
 * 返回:
 * 3
 * 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
 * <p>
 * 思路：
 */

class Solution {
    int count = 0;

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return count;
        back(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);
        return count;
    }

    public void back(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        target -= root.val;
        if (target == 0) {
            count++;
        }
        back(root.left, target);
        back(root.right, target);
    }
}


/**
 * 二叉树的所有路径 不带"->"
 */
class BinaryTreePaths {
    List<String> res = new ArrayList<>();
    StringBuilder str = new StringBuilder();

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        str.append(root.val);
        if (root.left == null && root.right == null) {
            res.add(str.toString());
        }
        dfs(root.left);
        dfs(root.right);
        str.deleteCharAt(str.length() - 1);
    }
}

/**
 * 257. 二叉树的所有路径
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [1,2,3,null,5]
 * 输出：["1->2->5","1->3"]
 * 示例 2：
 * <p>
 * 输入：root = [1]
 * 输出：["1"]
 */
class binaryTreePaths {
    List<String> res = new ArrayList<>();
    StringBuilder string = new StringBuilder();

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, "");
        return res;
    }

    public void dfs(TreeNode root, String s) {
        if (root == null) {
            return;
        }
        //注意这里，减少回溯时删去字符串的困难
        StringBuilder str = new StringBuilder(s);
        str.append(root.val);
        if (root.left == null && root.right == null) {
            res.add(str.toString());
        }
        str.append("->");
        dfs(root.left, str.toString());
        dfs(root.right, str.toString());
    }
}

/**
 * 404. 左叶子之和
 * 计算给定二叉树的所有左叶子之和。
 * <p>
 * 示例：
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * <p>
 * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 * <p>
 * 思路：层序遍历，每一层判断他的左节点有没有，有的话判断它是不是叶子节点，是的话就加入判断
 */
class sumOfLeftLeaves {
    public int sumOfLeftLeaves(TreeNode root) {
        //层序遍历，每一层判断他的左节点有没有，有的话判断它是不是叶子节点，是的话就加入判断
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 0;
        while (queue.size() > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    if (node.left.left == null && node.left.right == null) count += node.left.val;
                    queue.add(node.left);
                }
                if (node.right != null) queue.add(node.right);
            }
        }
        return count;
    }
}
